package com.aqie.easy.binarySearchTree;

import com.aqie.easy.structure.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * 653 bst 中找到两数和等于指定目标
 * 返回二叉搜索树最大值 和最小值 todo important
 * 中序遍历二叉树 将值存进数组
 *
 */
public class FindTarget {
    static int min = 0;
    // 双指针对撞
    ArrayList<Integer> list = new ArrayList<>();
    public boolean findTarget(TreeNode root, int k) {
        if (root == null) return false;
        inOrder(root);
        int size = list.size();
        if (size < 2 || list.get(0) + list.get(1) > k
                || list.get(size-1) + list.get(size-2) < k) return false;
        int l = 0, r = size - 1;
        while (l < r){
            int val = list.get(l) + list.get(r);
            if (val == k) return true;
            else if (val < k) l++;
            else r--;
        }
        return false;
    }

    private  void inOrder(TreeNode node){
        if (node != null) {
            inOrder(node.left);
            list.add(node.val);
            inOrder(node.right);
        }
    }

    private static void getMin(TreeNode root){
        if (root != null){
            min = root.val;
            getMin(root.left);

        }
    }

    /**
     * Hash
     * @param root
     * @param k
     * @return
     */
    public boolean findTarget3(TreeNode root, int k) {
        HashSet<Integer> hashset = new HashSet<Integer>();
        return preOrder(root,hashset,k);

    }

    public boolean preOrder(TreeNode root,HashSet<Integer> hashset,int k){
        if(root == null)
            return false;
        if(hashset.contains(k - root.val)){
            return true;
        }
        hashset.add(root.val);
        return preOrder(root.left,hashset,k) || preOrder(root.right,hashset,k);
    }

    /**
     * DFS
     * 寻找 BST 中的某个值的节点
     */

    public boolean findTarget2(TreeNode root, int k) {
       return preOrder(root,root,k);

    }
    public TreeNode findV(TreeNode node,int v){
        if (node == null) return null;
        if (node.val == v) return node;
        if (v < node.val) return findV(node.left,v);
        else return findV(node.right,v);
    }
    public boolean preOrder(TreeNode node,TreeNode root,int k){
        if (node == null) return false;
        int target = k - node.val;
        TreeNode foundNode =  findV(root,target);

        if(foundNode != null && node != foundNode) return true;
        else{
            return preOrder(node.left,root, k) || preOrder(node.right,root,k);
        }
    }



    public static void main(String[] args) {
        TreeNode node = new TreeNode(5);
        node.left = new TreeNode(3);
        node.right = new TreeNode(6);

        node.left.left = new TreeNode(2);
        node.left.right = new TreeNode(4);

        node.right.right = new TreeNode(7);
        getMin(node);
        System.out.println(min);
    }
}
